#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File    : sort.py
@Time    : 2022/11/20 19:38:19
@Author  : 郭瑞强
@Contact : sunraing@126.com
@Version : 0.1
@License : BSD 3-Clause License
@Desc    : 排序算法
"""


def cmp_fun(asc):
    def cmp_x_y(x, y):
        if asc:
            return x > y
        return x < y

    return cmp_x_y


# 暴力排序
def violence_sort(lis, asc=True):
    cmp = cmp_fun(asc)
    # 只需要进行lenth-1的排序
    for i in range(len(lis) - 1):
        for j in range(i + 1, len(lis)):
            if cmp(lis[i], lis[j]):
                lis[i], lis[j] = lis[j], lis[i]


# 冒泡排序
def bubble_sort(lis, asc=True):
    cmp = cmp_fun(asc)
    for i in range(len(lis) - 1, 0, -1):
        for j in range(i):
            if cmp(lis[j], lis[j + 1]):
                lis[j], lis[j + 1] = lis[j + 1], lis[j]


# 快速冒泡排序
def short_bubble_sort(lis, asc=True):
    cmp = cmp_fun(asc)
    exchange = True
    for i in range(len(lis) - 1, 0, -1):
        if not exchange:
            break
        exchange = False
        for j in range(i):
            if cmp(lis[j], lis[j + 1]):
                exchange = True
                lis[j], lis[j + 1] = lis[j + 1], lis[j]


# 选择排序
def selection_sort(lis, asc=True):
    cmp = cmp_fun(asc)
    for i in range(len(lis) - 1, 0, -1):
        m = 0
        for j in range(1, i + 1):
            if cmp(lis[j], lis[m]):
                m = j
        if m != i:
            lis[i], lis[m] = lis[m], lis[i]


# 插入排序
def insertion_sort(lis, asc=True):
    # 因为是从前向后排，故尔比较逻辑与上面几种相反
    cmp = cmp_fun(not asc)

    for pos in range(1, len(lis)):
        cur_val = lis[pos]
        pre_pos = pos - 1
        while pre_pos >= 0 and cmp(cur_val, lis[pre_pos]):
            lis[pre_pos + 1] = lis[pre_pos]
            pre_pos -= 1
        lis[pre_pos + 1] = cur_val


# 希尔排序
def shell_sort(lis, asc=True):
    cmp = cmp_fun(not asc)
    # cmp = lambda x, y: x < y if asc else x > y
    lenth = len(lis)
    gap = lenth // 2
    while gap > 0:
        # gap个子表，每个子对应起始位置为0,1,...,gap-1
        for g in range(gap):
            # 子表插入排序
            for pos in range(g + gap, lenth, gap):
                cur_val = lis[pos]
                pre_pos = pos - gap
                while pre_pos >= g and cmp(cur_val, lis[pre_pos]):
                    lis[pre_pos + gap] = lis[pre_pos]
                    pre_pos -= gap
                lis[pre_pos + gap] = cur_val

        gap = gap // 2


def merge_sort(lis, asc=True):
    cmp = cmp_fun(not asc)
    # cmp = lambda x, y: x < y if asc else x > y
    if len(lis) > 1:
        middle = len(lis) // 2
        left_part, right_part = lis[0:middle], lis[middle:]  # 这是个拷贝，有额外的内存开销

        merge_sort(left_part)
        merge_sort(right_part)

        k = 0  # lis列表可以重新利用
        while left_part and right_part:
            if cmp(left_part[0], right_part[0]):
                lis[k] = left_part.pop(0)
            else:
                lis[k] = right_part.pop(0)
            k += 1

        while left_part:
            lis[k] = left_part.pop(0)
            k += 1

        while right_part:
            lis[k] = right_part.pop(0)
            k += 1


def merge_em_sort(lis, asc=True):
    cmp = cmp_fun(not asc)
    # cmp = lambda x, y: x < y if asc else x > y
    if len(lis) > 1:
        middle = len(lis) // 2
        left_part, right_part = lis[0:middle], lis[middle:]  # 这是个拷贝，有额外的内存开销

        merge_sort(left_part)
        merge_sort(right_part)

        k = len(lis) - 1  # list列表pop()的时间消耗最小，改为pop()弹最后一个元素缩小排序时间
        while left_part and right_part:
            if cmp(left_part[-1], right_part[-1]):
                lis[k] = right_part.pop()
            else:
                lis[k] = left_part.pop()
            k -= 1

        while left_part:
            lis[k] = left_part.pop()
            k -= 1

        while right_part:
            lis[k] = right_part.pop()
            k -= 1


def merge_nr_sort(lis):
    from math import log2, ceil

    length = len(lis)
    n = ceil(log2(length))
    step = 2
    hstep = 1
    for k in range(n):
        if k == 0:  # 只有一个元素，顺序不对直接交换
            for idx in range(0, length, step):
                if lis[idx + 1] < lis[idx]:
                    lis[idx + 1], lis[idx] = lis[idx], lis[idx + 1]
        else:
            for idx in range(0, length, step):
                left_part = lis[idx: (idx + hstep)]
                right_part = lis[(idx + hstep): (idx + step)]
                idt = idx + len(left_part) + len(right_part) - 1
                while left_part and right_part:
                    if left_part[-1] < right_part[-1]:
                        lis[idt] = right_part.pop()
                    else:
                        lis[idt] = left_part.pop()
                    idt -= 1

                while left_part:
                    lis[idt] = left_part.pop()
                    idt -= 1

                while right_part:
                    lis[idt] = right_part.pop()
                    idt -= 1
        hstep = step
        step = step << 1


# 快速排序
def quick_sort(lis, first=None, last=None):
    first = 0 if not isinstance(first, int) else first
    last = len(lis) - 1 if not isinstance(last, int) else last
    if first < last:
        sp_point = partition(lis, first, last)
        quick_sort(lis, first, sp_point - 1)
        quick_sort(lis, sp_point + 1, last)


def partition(lis, first, last) -> int:
    pivot_v = lis[first]
    left_p = first + 1
    right_p = last

    done = False
    while not done:
        while left_p <= right_p and lis[left_p] < pivot_v:
            left_p += 1

        while right_p >= left_p and lis[right_p] >= pivot_v:
            right_p -= 1

        if right_p < left_p:
            done = True
        else:
            lis[left_p], lis[right_p] = lis[right_p], lis[left_p]

    lis[first], lis[right_p] = lis[right_p], lis[first]
    return right_p
